package com.demo.java.OD351_400.OD397;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【孙悟空吃蟠桃(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146244459
 */
public class OdMain {
    public static void main(String[] args) {
        // 读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取桃堆大小数组
        String[] pileStrings = scanner.nextLine().split(" ");
        int[] piles = new int[pileStrings.length];
        for (int i = 0; i < pileStrings.length; i++) {
            piles[i] = Integer.parseInt(pileStrings[i]);
        }

        // 读取给定的最大时间
        int h = Integer.parseInt(scanner.nextLine());

        // 调用查找最优速度的方法并输出结果
        System.out.println(findOptimalSpeed(piles, h));
    }

    // 判断能否在给定时间内吃完所有桃子
    private static boolean canEatAll(int eatSpeed, int[] piles, int h) {
        int hoursNeeded = 0;
        for (int pile : piles) {
            // 计算当前速度下，吃完当前堆桃子所需的小时数，并累加
            hoursNeeded += Math.ceil((double) pile / eatSpeed);
        }
        // 如果总时间小于等于h，说明该速度是可行的
        return hoursNeeded <= h;
    }

    // 查找最优吃桃速度
    private static int findOptimalSpeed(int[] piles, int h) {
        // 如果堆数大于给定时间，则无法完成任务，返回0
        if (piles.length > h) {
            return 0;
        }

        // 设置二分查找的初始范围
        int minSpeed = 1;
        int maxSpeed = getMaxSpeed(piles);  // 获取最大堆大小作为最大速度
        int optimalSpeed = maxSpeed;

        // 使用二分查找来找到最优速度
        while (minSpeed <= maxSpeed) {
            int mid = (minSpeed + maxSpeed) / 2;

            if (canEatAll(mid, piles, h)) {
                optimalSpeed = mid;  // 如果当前速度可行，尝试减小速度
                maxSpeed = mid - 1;
            } else {
                minSpeed = mid + 1;  // 如果当前速度不可行，增大速度
            }
        }

        return optimalSpeed;
    }

    // 获取最大的桃堆大小
    private static int getMaxSpeed(int[] piles) {
        int maxSpeed = Integer.MIN_VALUE;
        for (int pile : piles) {
            maxSpeed = Math.max(maxSpeed, pile);  // 找到最大堆
        }
        return maxSpeed;
    }
}